This invention relates generally to trellis decoders and more particularly to trellis decoders which produce soft decision (SD) outputs.
As is known in the art, trellis decoders are used in receivers of digital communication systems to reduce or eliminate errors caused by noise or distortion in a communication channel through which a sequence of data is transmitted. With such system, a coder is provided at the transmitter to encode the sequence of data into a sequence of symbols, each symbol representing an allowed transition from an originating trellis state of a state machine to a limited number of terminating trellis states. Referring to FIG. 1, the allowed transitions are shown for a state machine adapted to have four trellis states: S.sub.1, S.sub.2, S.sub.3, and S.sub.4. The coder encodes the sequence of data into a sequence of symbols; here symbols A.sub.1, A.sub.2, A.sub.3, and A.sub.4, such that:
symbol A.sub.1, represents an allowed transition from originating state S.sub.1 to terminating state S.sub.1, as a result of an input X, here 0, and from originating state S.sub.2 to terminating state S.sub.3 as a result of an input Y, here 1; PA1 symbol A.sub.2 represents an allowed transition from originating state S.sub.3 to terminating state S.sub.4 as a result of an input Y, here 1, and from originating state S.sub.4 to terminating state S.sub.2 as a result of an input X, here 0; PA1 symbol A.sub.3 represents an allowed transition from originating state S.sub.1 to terminating state S.sub.3 as a result of an input Y, here 1, and from originating state S.sub.2 to terminating state S.sub.1 as a result of an input X, here 0 and PA1 symbol A.sub.4 represents an allowed transition from originating state S.sub.3 to terminating state S.sub.2 as a result of an input X, here 0 and from originating state S.sub.4 to terminating state S.sub.4 as a result of an input Y, here 1. PA1 (i) For every starting state SI and corresponding end state S.sub.E compute the Euclidian distance D between the expected transition output symbol and the received symbol where the expected symbols take on the values {A.sub.1, A.sub.2, A.sub.3, A.sub.4 } as defined. This is carried out by a Branch Metric Calculation (BMC) Generation Unit. PA1 (ii) For every starting state SI and corresponding end state S.sub.E compute the sum of the branch metric (D) calculated in step (i) and the Accumulated Path Metric (APM) memory retained for that particular starting state S.sub.I from the previous transition. This is sum-compare-select function is performed by an Add-Compare-Select (ACS) unit. PA1 (iii) For each end state, retain only the transition which has produced the lowest sum G from all the possible start states to reach the end state S.sub.E and store it back in the Accumulated Path Metric (APM) memory. PA1 (iv) Repeat the procedure (i) to (iii) for every received symbol.
It should be noted that the current, (i.e., originating), state and the input value (i.e X or Y) specifies which symbols out of the entire set of symbols, here A.sub.1, A.sub.2, A.sub.3 and A.sub.4, may validly appear next in the sequence of transmitted symbols (i.e., the terminating state, or node, N). (For example, originating State S.sub.1 specifies that only symbols A.sub.1 and A.sub.3 may validly appear next in the sequence of symbols to be transmitted.) Thus, only selected sequences of transmitted symbols are permitted by the coding scheme. These permitted sequences are referred to as branches, here in this example, branches B.sub.1 -B.sub.8 in a trellis diagram shown in FIG. 1. Thus, each branch is defined by the originating state, the input value, the terminating state, and the symbol which uniquely represents the transition between such states. Thus, for example, from state S.sub.1 with an input value of Y, here 1, the only branch traversed is B.sub.2 to terminating state S.sub.3, and the only valid symbol which may exist in this transition through branch B.sub.2 is the symbol A.sub.3. (Note that irrespective of the starting (or initiating) state, two consecutive X inputs (i.e., here two consecutive inputs of 0) will bring the trellis to state S.sub.1, as this is a property of the trellis in this example, FIG. 2. Thus, the trellis shown in FIG. 1, having four trellis states S.sub.1 -S.sub.4 has two memory states MS, where 2.sup.MS =the number of trellis states).
Consider, as an example, that the symbols A.sub.1, A.sub.2, A.sub.3, and A.sub.4 are represented by values as follows: A.sub.1 =(+2, +2); A.sub.2 =(-2, +2); A.sub.3 =(-2, -2); and A.sub.4 =(+2, -2). Further, let the following sequence of input values is to be transmitted: